1. Field
One or more embodiments relate to an apparatus for reconfiguring, a mapping method and a scheduling method, and more particularly, to a mapping method and a scheduling method in a reconfigurable multi-processor system.
2. Description of the Related Art
A reconfigurable processor, which hereinafter will be referred to as an RP, can dynamically reconfigure hardware in a manner similar to the reconfiguration of software. In other words, various functions of hardware can be processed when a configuration is changed by a single RP. Since the RP meets requirements of application due to its performance that has advantages of hardware and due to its flexibility that is the advantage of software, it is expected to become widely used.
In general, the RP is a co-processor of a host processor and is used to accelerate the execution of a computationally intensive function.
However, in a multi-task environment where task creation and termination are dynamic, mapping for determining which function is to be executed in the RP and scheduling for executing the mapped function in the RP with minimum overhead are important technical issues for improving performance and usage rate.
A conventional mapping technique is a hardware-software sharing technique in which mapping between functions fa and fb of application and processors for executing the functions are dynamically determined at the time of the build-up of the application. However, when mapped applications are dynamically executed, various functions fa and fb may be mapped to a single reconfigurable processor 110 as illustrated in FIG. 1A.
In order to solve a problem caused by allocation of several functions to a single reconfigurable processor, a partial reconfiguration method “Remote and Partial Reconfiguration of FPGAs: tools and trends” has been disclosed by D. Mesquita et al., in the Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS'03), 2003, and a spatial-temporal sharing method using a multi-context has been suggested. However, such conventional methods do not suggest a fundamental solution due to resource constraints.
As an alternative to the conventional methods, a temporal sharing method has been proposed.
FIG. 1B illustrates an RP using temporal sharing according to the prior art.
Referring to FIGS. 1A and 1B, a function fa of a task tA 120 and a function fb of a task tB 130 are executed in the reconfigurable processor 110 using a temporal sharing method. In FIG. 1B, a dotted line indicates that a host processor 100 requests the reconfigurable processor 110 to perform reconfiguration to execute a specific function and a solid line indicates the host processor 100 requests the reconfigurable processor 110 to execute the specific function.
First, the task tA is executed in the host processor 100 at t0. At t1, the task tA calls the function fa, but it waits because the reconfigurable processor 110 is in the process of executing the function fb. At t2, the reconfigurable processor 110 reconfigures the function fa into a function fa. At t3, the reconfigurable processor 110 executes the function fa. At t4, the reconfigurable processor 110 provides a result of executing the function fa to the host processor 100. The task tB 130 is performed in the same manner as the task tA 120. Thereafter, the same process is repeated at intervals of T.
However, such a temporal sharing method increase the time and energy consumption required for execution due to the frequent reconfiguration of the reconfigurable processor. This is because execution time and energy consumption are caused by accessing memory when a new configuration bitstream is read and is overwritten to a configuration memory to reconfigure the reconfigurable processor. Referring to FIG. 1B, requests for the execution of the function fa and the function fb, which are made by the host processor 100 to the reconfigurable processor 110, are delayed by (t3−t2) or (t5−t4) due to the reconfiguration of the reconfigurable processor 110.
In order to reduce the delay, the configuration bitstream may be pre-fetched. To this end, however, a pre-fetch memory is additionally required, resulting in a failure to reduce energy consumption.
Another problem occurs when an existing function is being executed by the reconfigurable processor at the time of switching to another new function. Referring to FIG. 1B, at t1, the request for reconfiguration with respect to the function fa is delayed by (t2−t1) due to the ongoing execution of the function fb. In order to reduce the delay, preemptive scheduling may be performed. To this end, however, register values used by the reconfigurable processor have to be stored and then reconstructed later and this process consumes much time due to a large number of registers by nature of the reconfigurable processor.